/*************************************************************************
	> File Name: in_place_interleave.cpp
	> Author: likang
	> Mail: likang@ict.ac.cn
	> Created Time: 一  9/12 21:19:14 2016
 ************************************************************************/

#include<iostream>
#include<cmath>

using namespace std;


void rightRotate(int *arr, int low, int m, int high);

int getIndex(int a, int length) {
    if (a * 2 + 1 < length) {
        return a * 2 + 1;
    }
    else {
        return 2 * (length - 1 - a);
    }
}

//给定的数组是有序的且正负数都有(可升序可降序)
//本程序按照降序处理，升序只需改相关代码即可
//
void in_place_interleave_solution1(int *arr, int length) {
    int num = 0;         //记录数组中的负数个数
    for (int i = 0; i < length; ++i) {
        if (arr[i] < 0) {
            arr[i] = ~arr[i];
            ++num;
        }
    }
    cout << "num:" << num << endl;
    int count = 0;    //已经确定的元素的个数
    int tmp;
    for (int i = 0; count < length; ++i) {
        if (arr[i] < 0) {
            continue;
        }
        tmp = getIndex(i, length);
        int a = arr[i];
        
        while (arr[tmp] >= 0) {
            int b = arr[tmp];
            arr[tmp] = ~a;
            a = b;
            tmp = getIndex(tmp, length);
            ++count;
        } 
    }
    for (int i = 0; i < length; ++i) {
        arr[i] = ~arr[i];
    } 
    for (int i = 0; i < num; ++i) {
        arr[2 * i] = ~arr[2 * i];     
    }
}

//完美洗牌问题
//无论数组中是否有负数，无论是否排好序
//[a,b,c,d,e,f,g,h,y] -->[y,a,h,b,g,c,f,d,e]
//要点：当数组的长度为3的k次方减1的时候，数组重排列过后
//一共有k个环，每个环的起点是3的0次方减1到3的k-1次方减1
//当数组的长度不是恰好的时候，需要对数组进行调整，找到使长度等于
//3的k次方减1的子数组，假设为2m，在数组的前m个元素不动，将数组的后
//m个元素与中间的n-2m个元素交换位置，这样前2m个元素就可以满足完美洗牌
//依次对剩下的数组进行同样的改变
//
void in_place_interleave_solution2(int *arr, int low, int high) {

    int length = high - low + 1;
    if (length <= 1) {
        return;
    }
    int k = 0;
    while (length > pow(3, k) - 1) {
        ++k;
    }
    if (length != pow(3,k) - 1) {
        --k;
    }
    cout << "k : " << k << endl;
    
    int tmp_len = (pow(3,k) - 1) / 2;

    //进行数组调整
    rightRotate(arr, low, tmp_len, high);
    
    for (int i = 0; i < k; ++i) {
        int begin = pow(3,i) - 1;
        int next = -1;
        int pp = begin;
        int qq = arr[pp + low];

        while (next != begin) {
            next = getIndex(pp, 2 * tmp_len);
            int b = arr[next + low];
            arr[next + low] = qq;
            qq = b;
            pp = next;
        }
    }

    in_place_interleave_solution2(arr, low + 2 * tmp_len, high);
    return;

    
}

//循环右移m位
//作用将数组中间n-2m个数和末尾m个数进行调换
//现将中间n-2m个数反转，再将末尾m个数进行调换
//最后将数组末尾n-m个数反转
//
void rightRotate(int *arr, int low, int m, int high) {
    int tmp;
    for (int i = 0; i < m / 2; ++i) {
        tmp = arr[high - m + i + 1];
        arr[high - m + i + 1] = arr[high - i];
        arr[high - i] = tmp;
    }

    for (int i = 0; i < (high - low - 2 * m + 1) / 2; ++i) {
        tmp = arr[low + m + i];
        arr[low + m + i] = arr[high - m - i];
        arr[high - m - i] = tmp;
    }

    for  (int i = 0; i < (high - low - m + 1) / 2; ++i) {
        tmp = arr[low + m + i];
        arr[low + m + i] = arr[high - i];
        arr[high - i] = tmp;
    }
    cout << "-----------------" << endl;
    for (int i = 0; i <= high; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "-----------------" << endl;
    return ;
}

int main(void) {
    int arr[] = {7,6,5,4,3,2,1};
    int arr1[] = {7,6,5,4,-1,-2,-3};
    in_place_interleave_solution1(arr, 7);
    in_place_interleave_solution1(arr1, 7);

    for (int i = 0; i < 7; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < 7; ++i) {
        cout << arr1[i] << " ";
    }

    cout << endl;
    int arr2[] = {1,2,3,5,4,7,8,9,11,22,223,12};
    in_place_interleave_solution2(arr2, 0, 11);
    for (int i = 0; i < 12; ++i) {
        cout << arr2[i] << " ";
    }
    cout << endl;

}
